The beauty of Lambda Calculus
Have you ever heard of a Turing Machine?
A Turing Machine is an abstract model which can perform any function that is algorithmically computable.
Lambda calculus is Turing Complete, which means has the same computational power as a Turing Machine does.
In simpler terms, it is a full-functional way of representing data, performing operations on them and returning the expected result... but here's the catch: It's all functions. The whole system is just a bunch of functions, which take functions and return functions. Even the numbers are represented as functions. And that's amazing.
Let's outline the syntax, here is the simplest, useful lambda function:
We show data flow by simply putting the input (function) and the applied function together.
Here, the function
What would be the order? Let's say for now we settle it to prioritize the leftmost operations. So first
Here is another one
This one, accepts
Just a reminder, everything is a function here. The above lambda function doesn't even have any name. We have put
So, how do we represent numbers?
Here is the idea. We don't have numbers, but, we do have functions at our hand. We have to somehow manifest the nature of numbers within a function. How about this, we take two inputs and apply the first one
for instance,
Now, let's say we want a function which accepts a number
How do we do that? simply by using another
Question 1: What is doing here?
Answer: As we said, these Church numbers (here
Question 2: How does paratheses work in Lambda Calculus?
Answer: Intuitively, they determine the operation order we wish to preserve.
So, our
Now, let's say we want to add two numbers together.
Here is how we do it:
Question: What is the order here?
As mentioned above, unless we have parenthesis, the correct order is the leftmost function and leftmost inputs going through it. Therefore,
The result, is that (based on the specific definition of our number here) the number
Now how to do multiplication?
Here,
See! this is great! We can eventually define any function we desire, purely in terms of functions. For instance, in order to define subtraction, we would define a predecessor function and call it as many times as needed.
We can even represent logical expressions here. Let's assume we define
as the equivalent of TRUE. What it does, is that it takes two inputs and returns the first one. Now the way it could be used as TRUE isn't that intuitive here, but let's add
Now what would happen if we define conditions as :
It's taking three parameters and performing the first one on the last two. But hey, if we give our
And this is beautiful. The internal mechanism behind this world is the same as ours, even though basic concepts like numbers are not innately present in it. We merely need to carefully demonstrate the nature behind our familiar concepts using functions.